Images, such as charts, drawings, and pictures, may be represented as a two-dimensional matrix of picture elements (pixels). The spatial resolution and intensity level for each pixel are chosen to correspond to the particular output device used. For example, typical computer monitors display images at 75 dots per inch (DPI) and have 256 levels of intensity for each color. Such monitors use the additive primary colors, red, green, and blue (RGB), which can be combined to produce millions of colors and also black.
Hardcopy output devices, such as color inkjet printers, are commonly provided with 3 color inks (cyan, magenta, yellow) or 4 color inks (CMY and black(k)). These printers eject droplets of ink to form dots on a medium. Such printers cannot print colors having 256 levels of intensity and must use halftoning so that the overall color tone in an area on the medium closely matches that of the original image for that area. Halftoning methods are described in the book Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, incorporated herein by reference.
One major approach to halftoning is error diffusion. The decision about whether or not to print a dot of a particular color (or how many overlapping dots of a color to print) is based not only on the "ideal" intensity (i.e., one of the 256 possible intensities for a color) for that pixel, but on what has happened before for previously processed pixels. The present invention is directed to an error diffusion technique.
It is assumed in the following explanation that the pixel intensity may range between 0 and 255 and that a simple binary printer (dot or no dot for a pixel) is used. In error diffusion, at each point where a dot may be printed, the original image pixel intensity between 0-255, plus accumulated error, is compared to a previously chosen threshold value. If the image pixel intensity is greater than the threshold value, a dot (255 intensity) is assigned to that pixel. If not, no dot (0 intensity) is assigned. In either case, the intensity difference between the actual dot value assigned (0 or 255) and the ideal image pixel intensity plus accumulated error for that point is derived, and this difference becomes an error term that is "diffused" to neighboring, subsequently processed pixels. In other words, the diffused error term is added to the neighboring pixels. The total resultant image pixel intensity for the next pixel (including the diffused error) is then compared against the error diffusion threshold to determine whether a dot should be printed. A typical threshold value is 50% of the maximum theoretical image pixel intensity. For example, if there are 256 intensity levels (0 to 255) per pixel, a level of 128 may be chosen as the threshold value. In other error diffusion techniques, the threshold varies to avoid noticeable dot patterns being printed.
A well known error diffusion technique is described by R. Floyd and L. Steinberg in the paper Adaptive Algorithm for Spatial Grey Scale, SID Int'l. Sym. Digest of Tech. Papers, pp. 36-37 (1975), incorporated herein by reference. The Floyd and Steinberg error diffusion technique diffuses the error into a set of four surrounding pixels. Error diffusion with higher than four terms can also be used. U.S. Pat. No. 5,313,287 to David Barton, assigned to the present assignee and incorporated herein by reference, discloses another error diffusion technique.
When printing a color image, dots for three primary colors, cyan, magenta, and yellow, must be printed in various combinations to achieve the desired color tones to reproduce the original color image. Multiple dots of the same color may be used for a single color spot to increase the intensity of that color in the color spot.
Current Hewlett-Packard inkjet printers attempt to reproduce a near-continuous (256-level) input tone for a pixel location (cell) with relatively few primary output color levels, typically 2 to 4 levels per color. As a simplified example, a 4-level printer would be capable of printing levels for a single color ink designated 0, 1, 2, and 3, corresponding to, for example, 0, 1, 2, and 3 drops, respectively, of a single color ink per addressable cell. Other correlations between the color level 0-3 and the drops per level may be used. The base, or minimum, level to print in a current cell is determined by comparing the input tone value to a series of output level thresholds, or equivalently, taking the input tone value, scaling the value to the range of the output levels (e.g., a tone value of 1 equals 3/256), and taking the integer portion. For example, an input tone level of 128 would have a base output level of 128*3/256=1 drop. This produces an actual printed tone level of 1*255/3 or 85. In one type of error diffusion method, the remainder (128-85=43) is then added to the current error for the cell, and the accumulated error is compared to a threshold value to determine if the base level should be incremented by one. If the base level is incremented, the error is then recalculated and passed on to the appropriate neighboring cells.
The algorithm becomes more complicated as different numbers of output levels are used and different, and possibly asymmetric, output level thresholds are specified. This requires many specialized functions, as well as somewhat costly computations in figuring base levels and error terms.